package Tree;

//通过前序和中序序列创建二叉树
public class CreateByPreAndIn {

	public static void main(String[] args) {
//		int[] pre = { 1, 2, 3, 4, 5 };
//		int[] in = { 2, 4, 3, 5, 1 };
		int[] pre = { 1, 2, 3};
		int[] in = { 3, 1, 2};
		TreeNode node = reConstructBinaryTree(pre, in);
		PrintByDown.printFromTopToBottom(node); //还是有个小小的不足，只有当数据满足条件时才可以构建完整
	}

	public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
		if (pre.length == 0 || in.length == 0 || pre.length != in.length) {
			return null;
		}
		for (int i = 0; i < in.length; i++) {
//			System.out.print(i);
			// 首先找到根节点
			if (in[i] == pre[0]) {
				// 构建根节点
				TreeNode root = new TreeNode(in[i]);
				// 中序中 的 根节点左边的是左孩子，右边的为右孩子
				// 左孩子的数组
				int[] leftArrayIn = new int[i];
				int[] leftArrayPre = new int[i];
				for (int j = 0; j < i; j++) {
					leftArrayIn[j] = in[j];
				}
				for (int j = 0; j < i; j++) {
					leftArrayPre[j] = pre[j + 1];
				}
				// 右孩子的数组
				int[] rightArrayIn = new int[in.length - i - 1];
				int[] rightArrayPre = new int[in.length - i - 1];
				for (int j = i + 1; j < in.length; j++) {
					rightArrayIn[j - i - 1] = in[j];
				}
				for (int j = i + 1; j < pre.length; j++) {
					rightArrayPre[j - i - 1] = pre[j];
				}
				root.left = reConstructBinaryTree(leftArrayPre, leftArrayIn);
				root.right = reConstructBinaryTree(rightArrayPre, rightArrayIn);
				return root;
			}
			// 说明中序结点和前序结点不匹配，无输出
		}
		return null;
	}
}
